package com.dmall.chapter03.section04;

import java.util.*;

/**
 * 排序 + 双指针
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n)
 * @author xiao1.wang
 * @date 2020-12-01 23:14:47
 */
public class Leetcode15V2 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 去掉重复情况
                continue;
            }
            int left = i + 1, right = nums.length - 1;
            int target = -nums[i];
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        // 这里需要注意是right + 1, 因为right已经减减了
                        right--;
                    }
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int[] nums = {-5, 1, -10, 2, -7, -13, -3, -8, 2, -15, 9, -3, -15, 13, -6, -10, 5, 6, 11, 1, 13, -12, 14, 6, 11, 4, 13, -14, 0, 11, 1, 10, -11, 6, -11, -10, 8, 2, -3, -13, -6, -9, -9, -6, 11, -8, -9, 1, 13, 9, 9, 3, 13, 0, -6, 1, -10, -15, 3, 5, 3, 11, -8, 0, 2, -11, 5, -13, 6, 9, -11, 7, 8, -13, 8, 4, -6, 14, 13, -15, 1, 7, -5, -1, -7, 5, 7, -2, -3, -13, 10, 7, 13, 9, -8, -8, 13, 12, -6, 4, 7, -10, -12, -8, -8, 11, 11, -6, 3, 9, -14, -11, 2, -4, -5, 10, 8, -13, -7, 12, -10, 10};
        Leetcode15V2 leetcode15 = new Leetcode15V2();
        System.out.println(leetcode15.threeSum(nums));
        long end = System.currentTimeMillis();
        System.out.println((end - start));
    }
}
